/**
 * @FileName: 540_single_element_in_a_sorted_array.go
 * @Description: 540. 有序数组中的单一元素
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。



示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

https://leetcode-cn.com/problems/single-element-in-a-sorted-array/

 * @Author: shouzimu
 * @Date: 2022/2/14 10:34
*/

package main

import "fmt"

/**
24ms

题目要求  O(log n)  那就是二分了
*/
func singleNonDuplicate(nums []int) int {
	nlen := len(nums)
	if nlen == 1 {
		return nums[0]
	}

	if nums[0] != nums[1] {
		return nums[0]
	}

	if nums[nlen-1] != nums[nlen-2] {
		return nums[nlen-1]
	}

	l, r := 0, len(nums)-1

	for l <= r {
		mid := (l + r) / 2
		if nums[mid] != nums[mid+1] && nums[mid] != nums[mid-1] {
			return nums[mid]
		}
		if mid%2 == 0 {
			if nums[mid] != nums[mid+1] {
				r = mid - 1
			} else {
				l = mid + 1
			}
		} else {
			if nums[mid] != nums[mid-1] {
				r = mid - 1
			} else {
				l = mid + 1
			}
		}
	}
	return 0
}

func singleNonDuplicate2(nums []int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r) / 2
		if mid%2 == 0 {
			if nums[mid] != nums[mid+1] {
				r = mid
			} else {
				l = mid + 1
			}
		} else {
			if nums[mid] != nums[mid-1] {
				r = mid
			} else {
				l = mid + 1
			}
		}
	}
	return nums[l]
}

func main() {
	fmt.Println(singleNonDuplicate([]int{1, 1, 2, 3, 3}))
	fmt.Println(singleNonDuplicate([]int{3, 3, 7, 7, 10, 11, 11}))
	fmt.Println(singleNonDuplicate([]int{1, 1, 2, 3, 3, 4, 4, 8, 8}))
	fmt.Println(singleNonDuplicate([]int{1}))
	fmt.Println(singleNonDuplicate([]int{1, 1, 2}))
}
